package main

import "sort"

//给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
//
// 返回这三个数的和。
//
// 假定每组输入只存在恰好一个解。
//
//
//
// 示例 1：
//
//
//输入：nums = [-1,2,1,-4], target = 1
//输出：2
//解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
//
//
// 示例 2：
//
//
//输入：nums = [0,0,0], target = 1
//输出：0
//
//
//
//
// 提示：
//
//
// 3 <= nums.length <= 1000
// -1000 <= nums[i] <= 1000
// -10⁴ <= target <= 10⁴
//
// Related Topics 数组 双指针 排序 👍 1036 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
func threeSumClosest(nums []int, target int) int {
	result := nums[0] + nums[1] + nums[2]

	update := func(cur int) {
		if abs(target - cur) < abs(target - result) {
			result = cur
		}
	}

	sort.Ints(nums)
	for a := 0; a < len(nums); a++ {
		if a > 0 && nums[a] == nums[a-1] {
			continue
		}
		// nums[b] + num[c] 接近 target - num[a]
		for b := a + 1; b < len(nums); b++ {
			if b > a + 1 && nums[b] == nums[b - 1] {
				continue
			}
			for c := len(nums) - 1; c > b; c-- {
				cur := nums[a] + nums[b] + nums[c]
				if cur < target {
					update(cur)
					break
				}
				if cur == target {
					return cur
				}
				update(cur)
			}
		}
	}

	return result
}

func abs(a int) int {
	if a > 0 {
		return a
	} else {
		return -1 * a
	}
}
//leetcode submit region end(Prohibit modification and deletion)

